package day_2022_12_to_3.year2023;

/**
 * @author haomin
 * @date 2023/03/27 20:51
 **/
public class Day3_27_Review {
    class Solution1 {
        public int minArray(int[] numbers) {
            int l = 0, r = numbers.length-1, mid;
            while(l < r) {
                mid = l + ((r-l)>>1);
                if(numbers[mid] < numbers[r]) r = mid;
                else if(numbers[mid] > numbers[r]) l = mid + 1;
                else r--;
            }
            return numbers[l];
        }
    }

    class Solution2 {
        public boolean exist(char[][] board, String word) {
            if(board.length == 0 || board[0].length == 0) return false;
            int m = board.length, n = board[0].length;
            for(int i = 0; i < board.length; ++i) {
                for(int j = 0; j < board[0].length; ++j) {
                    if(board[i][j] == word.charAt(0)) {
                        if(isTrue(board, m, n, i, j, word, 0)) return true;
                    }
                }
            }
            return false;
        }
        public boolean isTrue(char[][] board, int m, int n, int i, int j, String word, int len) {
            if(len >= word.length()) return true;
            if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(len)) return false;
            board[i][j] += 58;
            boolean istrue = isTrue(board, m, n, i-1, j, word, len+1)
                    || isTrue(board, m, n, i+1, j, word, len+1)
                    || isTrue(board, m, n, i, j-1, word, len+1)
                    || isTrue(board, m, n, i, j+1, word, len+1);
            board[i][j] -= 58;
            return istrue;
        }
    }

    public class Solution3 {
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
            int ans = 0;
            int len = 32;
            while(len-- > 0) {
                ans += n & 1;
                n >>= 1;
            }
            return ans;
        }
    }

    class Solution4 {
        public ListNode deleteNode(ListNode head, int val) {
            if(head == null) return head;
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode cur = dummyHead;
            while(cur.next != null && cur.next.val != val) cur = cur.next;

            if(cur.next != null) cur.next = cur.next.next;
            return dummyHead.next;
        }
    }

    class Solution5 {
        public int[] exchange(int[] nums) {
            int l = 0, r = nums.length-1;
            while(l < r) {
                while(l < r && nums[l] % 2 == 1) l++;
                while(l < r && nums[r] % 2 == 0) r--;
                if(l < r) {
                    swap(nums, l, r);
                }
            }
            return nums;
        }
        public void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    class Solution6 {
        public boolean isSubStructure(TreeNode A, TreeNode B) {
            if(A == null || B == null) return false;
            return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
        }
        public boolean isSame(TreeNode a, TreeNode b) {
            if(b == null) return true;
            if(a == null) return false;
            return a.val == b.val && isSame(a.left, b.left) && isSame(a.right, b.right);
        }
    }
}